#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


int count(int arr[], int m, int sum)
{
    vector<vector<int> > dp(sum+1, vector<int>(m, 0));
    for (int i = 0; i < m; i++) 
	dp[0][i] = 1;
	
    for (int i = 1; i <= sum; i++) {
	for (int j = 0; j < m; j++) {
	    int a =  j >= 1 ? dp[i][j-1] : 0;
	    a += i >= arr[j] ? dp[i-arr[j]][j] : 0;
	    dp[i][j] = a;
	}
    }
    return dp[sum][m-1];
}


//much better dp method
int count2(int arr[], int m, int sum)
{
    vector<int> dp(sum+1, 0);
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
	for (int j = arr[i]; j <= sum; j++) {
	    dp[j] += dp[j-arr[i]];
	}
    }	
    return dp[sum];
}

int main(int argc, char **argv)
{
    int i, j;
    int arr[] = {2,5,3,6};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count2(arr, m, 10));
    return 0;
}
